package com.lun.swordtowardoffer2.c05;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

	public static class ListNode{
		public int key;
		public int value;
		public ListNode next;
		public ListNode prev;
		
		public ListNode(){}
		
		public ListNode(int key, int value) {
			this.key = key;
			this.value = value;
		}
	}
	
	private int capacity;
	private ListNode head;
	private ListNode tail;
	private Map<Integer, ListNode> map;
	
	public LRUCache(int capacity) {
		if(capacity <= 0) throw new IllegalArgumentException();
		this.capacity = capacity;
		this.head = new ListNode();
		this.tail = new ListNode();
		
		this.head.next = this.tail;
		this.tail.prev = this.head;
		
		this.map = new HashMap<>();
	}
	
	public void put(int key, int value) {
		if(map.containsKey(key)) {
			moveToTail(map.get(key), value);
		}else {
			if(map.size() == capacity) {//到阈值，移除最近最少使用的
				ListNode tmp = head.next;
				map.remove(tmp.key);
				deleteNode(tmp);
			}
			
			ListNode newOne = new ListNode(key, value);
			map.put(key, newOne);
			
			insertToTail(newOne);
			
		}
	}
	
	
	public int get(int key) {
		ListNode node = map.get(key);
		
		if(node == null)
			return -1;
		
		moveToTail(node, node.value);
		
		return node.value;
	}

	private void moveToTail(ListNode node, int value) {
		node.value = value;
		deleteNode(node);
		insertToTail(node);
	}
	
	private void deleteNode(ListNode node) {
		node.prev.next = node.next;
		node.next.prev = node.prev;
	}
	

	private void insertToTail(ListNode node) {
		node.prev = tail.prev;
		node.next = tail;
		tail.prev.next = node;
		tail.prev = node;
	}
	
}
